package 基础篇;

public class 双边循环快排 {
    public static void main(String[] args) {
        int[] array = {4,1,7,2,9,6,12,10};
        paixu(array, 0, array.length-1);
        for (int i : array) {
            System.out.println(i);
        }
    }

    static void paixu(int[] array, int leftIndex, int rightIndex){
        if(leftIndex >= rightIndex){
            return ;
        }
        // 第一轮循环
        int calculate = calculate(array, leftIndex, rightIndex);
        paixu(array, leftIndex, calculate-1);
        paixu(array, calculate +1 , rightIndex);
    }

    static int calculate(int[] array, int leftIndex, int rightIndex){
        // 边界值
        int maxIndexValue = array[leftIndex];
        int l = leftIndex;
        int r = rightIndex;
        while(l <r){
            while(l <r && array[r] > maxIndexValue){
                r--;
            }
            while(l <r && array[l] <= maxIndexValue){
                l++;
            }
            swap(array, l, r);
        }
        swap(array, leftIndex, r);
        return r;

    }

    static void swap(int[] array, int startIndex, int endIndex){
        int a = array[startIndex];
        array[startIndex] = array[endIndex];
        array[endIndex] = a;
    }
}
